/**
 * @author 徐梦轲
 * @data 2022/5/26 0026 - 11:13
 */

import java.util.Stack;

/**
 *
 * @author     ：徐梦轲
 * @date       ：2022/5/26 0026 11:13
 */

public class Solution {
    //解法1：利用辅助栈+正向思维
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (isOperation(s.charAt(i))) {
                stack.push(s.charAt(i));
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                if (judge(stack.peek(),s.charAt(i))) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
    public boolean isOperation(char ch) {
        return (ch == '(' || ch == '{' || ch == '[');
    }
    public boolean judge (char ch1,char ch2) {
        if (ch1 == '(' && ch2 == ')') {
            return true;
        }
        if (ch1 == '[' && ch2 == ']') {
            return true;
        }
        return ch1 == '{' && ch2 == '}';
    }

    //解法2：利用辅助栈+逆向思维
    public boolean isValid2(String s) {
        Stack<Character>stack = new Stack<Character>();
        for(char c: s.toCharArray()){
            if(c=='('){
                stack.push(')');
            }
            else if(c=='['){
                stack.push(']');
            }
            else if(c=='{'){
                stack.push('}');
            }
            else if(stack.isEmpty()||c!=stack.pop()){
                return false;
            }
        }
        return stack.isEmpty();
    }
}
